import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 排序算法
 */
public class Test {
    public static void main(String[] args) {
        int[] array = {2,56,23,18,20,198,120};
        //insertSort(array);
        shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
        //quickSort(array);
        //mergeSort1(array);
        //mergeSort2(array);
        //countSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 插入排序
     * 时间复杂度：O(N ^ 2)
     * 空间复杂度：O(N)
     * 稳定排序
     * @param array
     */
    public static void insertSort(int[] array) {
        //write code  here
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for(; j >= 0; j--) {
                if(tmp >= array[j]) {
                    array[j + 1] = tmp;
                    break;
                }else {
                    array[j + 1] = array[j];
                }
            }
            if(j < 0) {
                array[0] = tmp;
            }
        }
    }

    /**
     * 希尔排序每次确定的增量排序（以插入排序为基础）
     * @param array 需要排序的数组
     * @param gap 每次排序（预排序的增量）
     */
    public static void insertSort(int[] array,int gap) {
        //write code  here
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(tmp >= array[j]) {
                    array[j + gap] = tmp;
                    break;
                }else {
                    array[j + gap] = array[j];
                }
            }
            if(j < 0) {
                array[j + gap] = tmp;
            }
        }
    }

    /**
     * 希尔排序（缩小增量排序）
     * 由于数学上尚未得到对希尔排序的增量最优的取值，因此时间复杂度无法计算
     * 不过可以记住近似O(N ^ 1.3)
     * 空间复杂度：O(1)
     * 不稳定排序
     * @param array
     */
    public static void shellSort(int[] array){
        // write code  here
        int gap = array.length / 2;
        while(gap > 0) {
            insertSort(array,gap);
            gap /= 2;
        }
    }

    /**
     * 选择排序
     * 时间复杂度为：O(N ^ 2)
     * 空间复杂度为：O(1)
     * 不稳定排序：每次得到最大或最小值之后交换的时候可能会将本来在前面的数放在与该数相等的数的后面
     * @param array
     */
    public static void selectSort(int[] array){
        // write code  here
        for (int i = 0; i < array.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[min] > array[j]) {
                    min = j;
                }
            }
            if(min != i) {
                swap(array,min,i);
            }
        }
    }

    //向下调整
    private static void shiftDown(int[] array, int root, int len) {
        int child = root * 2 + 1;
        while(child < len) {
            if(child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if(array[root] < array[child]) {
                swap(array,root,child);
            }else {
                break;
            }
            root = child;
            child = root * 2 + 1;
        }
    }

    public static void creatHeap(int[] array) {
        int len = array.length;
        for(int i = (len - 2) / 2; i >= 0; i--) {
            shiftDown(array,i,len);
        }
    }

    /**
     * 底层代码实现堆排序
     * 创建堆由于是向下调整，时间复杂度为O(N)
     * 堆排序时堆顶元素和最后一个元素进行交换，后向下调整
     * 由于一半元素集中在叶子节点，因此向下调整一次的时间复杂度为O(logN)
     * 整个堆排序的时间复杂度就是O(N * logN) + O(N)（O(N)舍去）
     * 最终时间复杂度为O(N * logN)
     * 空间复杂度为O(1)
     * 不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        // write code  here
        creatHeap(array);
        int len = array.length;
        while(len > 1) {
            swap(array,0,len - 1);
            len--;
            shiftDown(array,0,len);
        }
    }

    /**
     * 利用 PriorityQueue 进行堆排序
     * @param array
     */
    public static void heapSort1(int[] array){
        // write code  here
        PriorityQueue<Integer> queue = new PriorityQueue(new Comparator<Integer>() {
            public int compare(Integer o1,Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < array.length; i++) {
            queue.offer(array[i]);
        }
        for (int i = array.length - 1; i >= 0; i--) {
            array[i] = queue.poll();
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度：O(N ^ 2)
     * 空间复杂度：O(1)
     * 稳定
     * @param array
     */
    public static void bubbleSort(int[] array){
        // write code  here
        //趟数
        for (int i = 0; i < array.length - 1; i++) {
            //比较次数
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j + 1);
                    flg = true;
                }
            }
            if(!flg){
                return;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度：O(NlogN)（快排时间复杂度不按照最坏情况计算）
     * 空间复杂度：O(logN)（函数栈帧的空间）
     * 不稳定
     * @param array
     * @param start
     * @param end
     */
    //版本一，元素交换法
    private static void quickSortChild1(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && array[right] >= array[start]) {
                right--;
            }
            while(left < right && array[left] <= array[start]) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,start,left);
        quickSortChild1(array,start,left - 1);
        quickSortChild1(array,left + 1,end);
    }

    //比较start mid end三者的值，尽量让start的值是中间值
    private static void setMid(int[] array,int start,int end) {
        int mid = (end - start) / 2 + start;
        if(array[start] < array[end]) {
            if(array[mid] < array[end] && array[mid] > array[start]) {
                swap(array,start,mid);
            }else if(array[mid] > array[end]) {
                swap(array,start,end);
            }
        } else {
            if(array[mid] < array[end]) {
                swap(array,start,end);
            }else if(array[mid] < array[start] && array[mid] > array[end]) {
                swap(array,start,mid);
            }
        }
    }

    //版本二
    //优化，尽量保证分治的二叉树是完全二叉树
    private static void quickSortChild2(int[] array,int start,int end) {
        if(end - start < 10) {
            insertSort(array);
            return;
        }
        //尽量保证分治的二叉树是完全二叉树
        setMid(array,start,end);
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && array[right] >= array[start]) {
                right--;
            }
            while(left < right && array[left] <= array[start]) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,start,left);
        quickSortChild2(array,start,left - 1);
        quickSortChild2(array,left + 1,end);
    }

    //版本三
    //挖坑法(最常用)
    private static void quickSortChild(int[] array,int start,int end) {
        if(end - start < 10) {
            insertSort(array);
            return;
        }
        //尽量保证分治的二叉树是完全二叉树
        setMid(array,start,end);
        int tmp = array[start];
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        quickSortChild(array,start,left - 1);
        quickSortChild(array,left + 1,end);
    }

    //版本四 快慢指针（完整）
    private void quickSort(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        int cur = start + 1;
        int prev = start;
        while(cur <= end) {
            while(cur <= end && arr[cur] <= arr[start]) {
                prev++;
                cur++;
            }
            while(cur <= end && arr[cur] > arr[start]) {
                cur++;
            }
            while(cur <= end && arr[prev + 1] <= arr[start]) {
                prev++;
            }
            while(cur <= end && arr[cur] <= arr[start] && arr[prev + 1] > arr[start]) {
                swap(arr, prev + 1, cur);
                prev++;
                cur++;
            }
        }
        swap(arr, start, prev);
        quickSort(arr, start, prev - 1);
        quickSort(arr, prev + 1, end);
    }

    //快慢指针精简版
    private void quickSort1(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        int cur = start + 1;
        int prev = start;
        while(cur <= end) {
            //相比较上面那种写法，这种写法可能会存在多次无用的交换
            //即当arr[cur] < arr[start] && arr[++prev] < arr[start]
            //并且cur != prev，这种情况下，就会发生无用的交换
            if(arr[cur] < arr[start] && arr[++prev] != arr[cur]) {
                swap(arr, cur, prev);
            }
            cur++;
        }
        swap(arr, start, prev);
        quickSort1(arr, start, prev - 1);
        quickSort1(arr, prev + 1, end);
    }

    //快慢指针极精简版
    private void quickSort2(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        int prev = start + 1;
        //比第二种更极端，只要arr[i] < arr[start]，就要交换
        //如果数组顺序是降序，那么每个都要自己和自己交换，最后prev == i == end + 1
        for(int i = start + 1; i <= end; i++) {
            if(arr[i] < arr[start]) {
                swap(arr, prev, i);
                prev++;
            }
        }
        //要保证与arr[start]交换的位置的值小于等于arr[start]，就用prev - 1位置的值
        swap(arr, start, prev - 1);
        //同理这里的边界也需要修改
        quickSort2(arr, start, prev - 2);
        quickSort2(arr, prev, end);
    }

    // 快速排序
    public static void quickSort(int[] array){
        // write code  here
        quickSortChild(array,0,array.length - 1);
    }

    //快速排序非递归版
    private void quickSort3(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(end);
        stack.push(start);
        while(!stack.empty()) {
            int left = stack.pop();
            int right = stack.pop();
            if(left >= right) {
                continue;
            }
            int tmp = arr[left];
            int curLeft = left;
            int curRight = right;
            while(curLeft < curRight) {
                while(curLeft < curRight && arr[curRight] >= tmp) {
                    curRight--;
                }
                arr[curLeft] = arr[curRight];
                while(curLeft < curRight && arr[curLeft] <= tmp) {
                    curLeft++;
                }
                arr[curRight] = arr[curLeft];
            }
            arr[curLeft] = tmp;
            stack.push(right);
            stack.push(curLeft + 1);
            stack.push(curLeft - 1);
            stack.push(left);
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(NlogN)
     * 空间复杂度：O(N)
     * 稳定
     * @param array
     * @param start
     * @param end
     */
    public static void mergeSortChild(int[] array,int start,int end) {
        int len = end - start + 1;
        if(len <= 1) {
            return;
        }
        int mid = (len - 1) / 2 + start;
        mergeSortChild(array,start,mid);
        mergeSortChild(array,mid + 1,end);
        int[] nums = new int[len];
        int left1 = start;
        int left2 = mid + 1;
        int i = 0;
        while(left1 <= mid && left2 <= end) {
            if(array[left1] <= array[left2]) {
                nums[i++] = array[left1++];
            }else {
                nums[i++] = array[left2++];
            }
        }
        while(left1 <= mid) {
            nums[i++] = array[left1++];
        }
        while(left2 <= end) {
            nums[i++] = array[left2++];
        }
        for (int j = 0; j < len; j++) {
            array[start + j] = nums[j];
        }
    }

    // 归并排序---递归
    public static void mergeSort(int[] array){
        // write code  here
        mergeSortChild(array,0,array.length - 1);
    }

    // 归并排序---非递归
    public static void mergeSort1(int[] array){
        // write code here
        int len = array.length;

        //i 作为递归的间隔
        for (int i = 2; i < len * 2; i *= 2) {
            //j 作为归并序列的开始位置
            //mid = (end - start) / 2 + start
            for (int j = 0; j < len; j = j + i) {
                int start = j;
                int end = j + i - 1;
                if(end >= len) {
                    end = len - 1;
                }
                int mid = (end - start) / 2 + start;
                int left1 = start;
                int left2 = mid + 1;
                int k = 0;
                int[] nums = new int[end - start + 1];
                while(left1 <= mid && left2 <= end) {
                    if(array[left1] <= array[left2]) {
                        nums[k++] = array[left1++];
                    }else {
                        nums[k++] = array[left2++];
                    }
                }
                while(left1 <= mid) {
                    nums[k++] = array[left1++];
                }
                while(left2 <= end) {
                    nums[k++] = array[left2++];
                }
                for (k = 0; k < end - start + 1; k++) {
                    array[start + k] = nums[k];
                }
            }
        }
    }

    //第二种，以mid来跳
    public static void mergeSort2(int[] array) {
        // write code here
        int len = array.length;
        for (int i = 1; i < len; i *= 2) {
            //j以2 * mid为标准跳，即直接跳过 end 与 start 之间的距离
            for (int j = 0; j < len; j = j + 2 * i) {
                //此时范围包括j,但不包括j + 2 * i
                //即前闭后开
                int end = j + 2 * i;
                if(end >= len) {
                    end = len;
                }
                int mid = j + i;
                //当mid >= len时，意味着要比较的两组数据后一组根本没有，而前一组已经有序
                //那么就直接continue
                if(mid >= len) {
                    continue;
                }
                int[] nums = new int[end - j];
                int left1 = j;
                int left2 = mid;
                int k = 0;
                while(left1 < mid && left2 < end) {
                    if(array[left1] <= array[left2]) {
                        nums[k++] = array[left1++];
                    }else {
                        nums[k++] = array[left2++];
                    }
                }
                while(left1 < mid) {
                    nums[k++] = array[left1++];
                }
                while(left2 < end) {
                    nums[k++] = array[left2++];
                }
                for (k = 0; k < end - j; k++) {
                    array[j + k] = nums[k];
                }
            }
        }
    }

    /**
     * 计数排序
     * 时间复杂度：O(N)
     * 空间复杂度：O(max - min)
     * 不稳定
     * @param array
     */
    public static void countSort(int[] array){
        // write code  here
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if(max < array[i]) {
                max = array[i];
            }
            if(min > array[i]) {
                min = array[i];
            }
        }
        int[] nums = new int[max - min + 1];
        for(int i = 0; i < array.length; i++) {
            nums[array[i] - min]++;
        }
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            while(nums[j] > 0) {
                array[i++] = j + min;
                nums[j]--;
            }
        }
    }

}
